// 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

// 示例 1:

// 输入: 2
// 输出: [0,1,1]
// 示例 2:

// 输入: 5
// 输出: [0,1,1,2,1,2]
// 进阶:

// 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
// 要求算法的空间复杂度为O(n)。
// 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。

#include <vector>

using namespace std;

/*
时间复杂度：O(n*size(k)), k是每个整数的位数
空间复杂度：O(n)
*/
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res(num + 1, 0);
        for (int i{1}; i <= num; ++i) {
            int n = i;
            while (n) {
                n = n & (n - 1);
                ++res[i];
            }
        }
        return res;
    }
};

/* 动态规划+最后设置位
利用已经计算过的结果
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res(num + 1, 0);
        for (int i{1}; i <= num; ++i) {
            res[i] = res[i & i-1] + 1;
        }
        return res;
    }
};

/* 动态规划+ 奇偶判断
dp[i]为i的二进制形式的1的个数，
i是奇数时，dp[i]=dp[i-1]+1,因为i是在i-1的二进制数上加了个1；
i是偶数时，dp[i]=dp[i/2],因为i就是把i/2往左移（是数左移，末尾补0）得到的，所以1的个数没变

时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> dp(num + 1, 0);
        for (int i{1}; i <= num; ++i) {
            if ((i & 1) == 0) { // 一定要加上括号，==的优先级比&高
                dp[i] = dp[i / 2]; // 偶数
            } else {
                dp[i] = dp[i - 1] + 1;
            }
        }
        return dp;
    }
};
